package bintree.leetcode;

import java.util.LinkedList;
import java.util.List;

/**
 * @Author: yuisama
 * @Date: 2022/10/8 16:10
 * @Description:构造不同的BST
 */
public class Num95_GenerateBSTrees {
    public List<TreeNode> generateTrees(int n) {
        return build(1,n);
    }

    /**
     * 在区间[lo..hi]上构造不同的BST，返回不同BST的树根
     * @param lo
     * @param hi
     * @return
     */
    private List<TreeNode> build(int lo, int hi) {
        List<TreeNode> list = new LinkedList<>();
        // base case
        if (lo > hi) {
            list.add(null);
            return list;
        }
        for (int i = lo; i <= hi; i++) {
            // 先构建出左右子树的结果集
            List<TreeNode> left = build(lo,i - 1);
            List<TreeNode> right = build(i + 1,hi);
            // 枚举左右子树，以当前i为树根
            for (TreeNode l : left) {
                for (TreeNode r : right) {
                    TreeNode root = new TreeNode(i);
                    root.left = l;
                    root.right = r;
                    list.add(root);
                }
            }
        }
        return list;
    }
}
